package com.formula.datastructure.exercise.sort.adv;


import com.formula.datastructure.standard.queue.Queue;
import com.formula.datastructure.util.DataUtil;

// 不需要申明辅助数组
public class BucketSort {

    public Integer[] sort(Integer[] input) {
        //calculate max digit
        int digit = 3;
        for (int i = 1; i <= digit; i++) {
            input = bucketSort(input, i);
        }

        return input;
    }

    /**
     * 思路就是每次把
     * @param array
     * @param digit
     * @return
     */
    private Integer[] bucketSort(Integer[] array, int digit) {

        int base = power(digit);

        Queue<Integer>[] buckets = new Queue[10];

        for (int i = 0; i < 10; i++) {
            buckets[i] = new Queue<>();
        }


        // digit是1, 也就是只计算个位
        for (int i = 0; i < array.length; i++) {
            // 先除以base, 再得到10的余数
            int bucketId = (array[i] / base) % 10;
            buckets[bucketId].enQueue(array[i]);
        }

        int idx = 0;
        for (int i = 0; i < 10; i++) {
            while (!buckets[i].isEmpty()) {
                array[idx++] = buckets[i].deQueue();
            }
        }

        return array;
    }

    // 如果输入是2, 就是2位数, 输出就是10
    private int power(int digit) {
        int result = 1;
        for (int i = 1; i < digit; i++) {
            result = result * 10;
        }
        return result;
    }

    public static void main(String[] args) {
        BucketSort bucket = new BucketSort();
        int size = 20;
        int range = 999;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);
        DataUtil.printArray(bucket.sort(array));
    }
}
